#include<iostream>
#include<ctime>
using namespace std;

// int main()
// {
//     srand(time(0));
//     int a[10]{};
//     for(int i = 0; i < 10; i++)
//     {
//         a[i] = rand() % 20;
//         cout << a[i] << ' ';
//     }
    
//     return 0;
// }
//12 4 17 0 1 5 15 16

#if 0
namespace Key
{
template<class K>
struct BSTree_node
{
    K _key;
    BSTree_node* _left;
    BSTree_node* _right;
    BSTree_node(const K& key, BSTree_node* left = nullptr, BSTree_node* right = nullptr)
        :_key(key)
        ,_left(left)
        ,_right(right)
    {}
};

template<class K>
class BSTree
{
    typedef BSTree_node<K> node;
    node* _root = nullptr;

    void _print(node* root)
    {
        if(!root) return;
        _print(root->_left);
        cout << root->_key << ' ';
        _print(root->_right);
    }
    void _clear(node* root)
    {
        if(!root) return;
        _clear(root->_left);
        _clear(root->_right);
        delete root;
    }
    node* copy(node* root)
    {
        if(!root) return nullptr;
        node* left = copy(root->_left);     // 拷贝左子树
        node* right = copy(root->_right);   // 拷贝右子树
        node* r = new node(root->_key);     // 拷贝root
        r->_left = left, r->_right = right; // 连接起来
        return r;
    }
public:
    // 无参构造，这里无需写_root = nullptr; 因为我已经给了缺省值
    BSTree() {}

    // 迭代器区间构造
    template<class InputIterator>
    BSTree(InputIterator first, InputIterator last) 
    {
        while(first != last)
        {
            insert(*first);
            ++first;
        }
    }

    ~BSTree()  { 
        clear(); 
        cout << "~BSTree()" << endl;
    }
    void clear() 
    { 
        _clear(_root); 
        _root = nullptr;
    }
    BSTree(const BSTree& t) { _root = copy(t._root); }
    void swap(BSTree& t)
    {
        std::swap(_root, t._root);
    }
    BSTree& operator= (const BSTree& t)
    {
        if(this != &t)
        {
            BSTree tmp(t);
            swap(tmp);
        }
        return *this;
    }

    node* find(const K& x)
    {
        node* root = _root;
        while(root)
        {
            if(x < root->_key) root = root->_left;
            else if(x > root->_key) root = root->_right;
            else break;
        }
        return root;
    }

    // 成功插入返回true，否则返回false
    bool insert(const K& x)
    {
        if(!_root)
        {
            _root = new node(x);
            return true;
        }
        node* root = _root;
        node* p = nullptr;
        while(root)
        {
            p = root;
            if(x < root->_key) root = root->_left;
            else if(x > root->_key) root = root->_right;
            else return false;
        }
        if(x < p->_key) p->_left = new node(x);
        else p->_right = new node(x);
        return true;
    }

    // 成功删除返回true，否则返回false
    bool erase(const K& x)
    {
        node* root = _root;
        node* p = nullptr;
        while(root)
        {
            if(x < root->_key) 
                p = root, root = root->_left;
            else if(x > root->_key) 
                p = root, root = root->_right;
            else{
                // 删除
                // 情况1，root为叶子节点
                if(!root->_left && !root->_right)
                {
                    if(!p) _root = nullptr; // 需要特判一下树中只有一个节点的情况
                    else if(root == p->_left) p->_left = nullptr;
                    else p->_right = nullptr;
                    delete root;
                    return true;
                }

                // 情况2，root只有一个儿子
                else if(!root->_left || !root->_right)
                {
                    node* child = root->_left ? root->_left : root->_right;

                    if(!p)  // 特判树根就是root的情况
                        _root = _root->_left ? _root->_left : _root->_right;
                    else if(root == p->_left) p->_left = child;
                    else p->_right = child;
                    delete root;
                    return true;
                }

                // 情况3，root有l两个儿子
                else{
                    // 找前驱
                    node* pre = root->_left;
                    node* pre_parent = root;
                    while(pre->_right) 
                    {
                        pre_parent = pre;
                        pre = pre->_right;
                    }
                    // 到这里，pre必定没有右儿子
                    root->_key = pre->_key;
                    if(pre_parent->_left == pre) pre_parent->_left = pre->_left;
                    else pre_parent->_right = pre->_left;
                    delete pre;
                    return true;
                }
            }
        }
        return false;
    }

    void print()
    {
        _print(_root);
        cout << endl;
    }
};

void test01()
{
    int a[10] = {12, 4, 17, 0, 1, 1, 5, 15, 16, 4};
    BSTree<int> t;
    BSTree<int> t1(a, a + 10);  // 迭代器构造
    t.print();
    t1.print();
}

void test02()
{
    int a[10] = {12, 4, 17, 0, 1, 1, 5, 15, 16, 4};
    BSTree<int> t1(a, a + 10);  // 迭代器构造
    t1.print();
    BSTree<int> t2(t1);
    t2.print();
}

void test03()
{
    int a[10] = {12, 4, 17, 0, 1, 1, 5, 15, 16, 4};
    BSTree<int> t1(a, a + 10);  // 迭代器构造
    t1.print();
    BSTree<int> t2;
    t2 = t1;
}
} // namespace Key

#endif

namespace KeyValue
{
template<class K, class V>
struct BSTree_node
{
    K _key;
    V _value;
    BSTree_node* _left;
    BSTree_node* _right;
    BSTree_node(const K& key, const V& val, BSTree_node* left = nullptr, BSTree_node* right = nullptr)
        :_key(key)
        ,_value(val)
        ,_left(left)
        ,_right(right)
    {}
};

template<class K, class V>
class BSTree
{
    typedef BSTree_node<K, V> node;
    node* _root = nullptr;

    void _print(node* root)
    {
        if(!root) return;
        _print(root->_left);
        cout << root->_key << ' ' << root->_value << endl;
        _print(root->_right);
    }
    void _clear(node* root)
    {
        if(!root) return;
        _clear(root->_left);
        _clear(root->_right);
        delete root;
    }
    node* copy(node* root)
    {
        if(!root) return nullptr;
        node* left = copy(root->_left);     // 拷贝左子树
        node* right = copy(root->_right);   // 拷贝右子树
        node* r = new node(root->_key);     // 拷贝root
        r->_left = left, r->_right = right; // 连接起来
        return r;
    }
public:
    // 无参构造，这里无需写_root = nullptr; 因为我已经给了缺省值
    BSTree() {}

    // 迭代器区间构造
    template<class InputIterator>
    BSTree(InputIterator first, InputIterator last) 
    {
        while(first != last)
        {
            insert(*first);
            ++first;
        }
    }

    ~BSTree()  { 
        clear(); 
        // cout << "~BSTree()" << endl;
    }
    void clear() 
    { 
        _clear(_root); 
        _root = nullptr;
    }
    BSTree(const BSTree& t) { _root = copy(t._root); }
    void swap(BSTree& t)
    {
        std::swap(_root, t._root);
    }
    BSTree& operator= (const BSTree& t)
    {
        if(this != &t)
        {
            BSTree tmp(t);
            swap(tmp);
        }
        return *this;
    }

    node* find(const K& x)
    {
        node* root = _root;
        while(root)
        {
            if(x < root->_key) root = root->_left;
            else if(x > root->_key) root = root->_right;
            else break;
        }
        return root;
    }

    // 成功插入返回true，否则返回false
    bool insert(const K& key, const V& val)
    {
        if(!_root)
        {
            _root = new node(key, val);
            return true;
        }
        node* root = _root;
        node* p = nullptr;
        while(root)
        {
            p = root;
            if(key < root->_key) root = root->_left;
            else if(key > root->_key) root = root->_right;
            else return false;
        }
        if(key < p->_key) p->_left = new node(key, val);
        else p->_right = new node(key, val);
        return true;
    }

    // 成功删除返回true，否则返回false
    bool erase(const K& key)
    {
        node* root = _root;
        node* p = nullptr;
        while(root)
        {
            if(key < root->_key) 
                p = root, root = root->_left;
            else if(key > root->_key) 
                p = root, root = root->_right;
            else{
                // 删除
                // 情况1，root为叶子节点
                if(!root->_left && !root->_right)
                {
                    if(!p) _root = nullptr; // 需要特判一下树中只有一个节点的情况
                    else if(root == p->_left) p->_left = nullptr;
                    else p->_right = nullptr;
                    delete root;
                    return true;
                }

                // 情况2，root只有一个儿子
                else if(!root->_left || !root->_right)
                {
                    node* child = root->_left ? root->_left : root->_right;

                    // 特判树根就是root的情况
                    if(!p)  _root = child;
                    else if(root == p->_left) p->_left = child;
                    else p->_right = child;
                    delete root;
                    return true;
                }

                // 情况3，root有两个儿子
                else{
                    // 找前驱
                    node* pre = root->_left;
                    node* pre_parent = root;
                    while(pre->_right) 
                    {
                        pre_parent = pre;
                        pre = pre->_right;
                    }
                    // 到这里，pre必定没有右儿子
                    root->_key = pre->_key;
                    if(pre_parent->_left == pre) pre_parent->_left = pre->_left;
                    else pre_parent->_right = pre->_left;
                    delete pre;
                    return true;
                }
            }
        }
        return false;
    }

    void print()
    {
        _print(_root);
        cout << endl;
    }
};

void test01()
{
    BSTree<string, string> h;
    h.insert("hello", "你好");
    h.insert("apple", "苹果");
    h.insert("tomato", "西红柿");
    auto pos = h.find("xxxx");
    if(!pos) cout << "未找到" << endl;
    else
        cout << pos->_value << endl;
}
} // namespace KeyValue



int main()
{
    KeyValue::test01();
    // BSTree<int> t;
    // int a[] = {12, 4, 17, 0, 1, 1, 5, 15, 16};
    // for(auto e : a)
    //     t.insert(e);
    // t.print();
    // BSTree<int> t1 = t;
    // t1.print();
    return 0;
}